//TODO: LeetCode145. 二叉树的后序遍历
//* 非递归

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ret;
        stack<TreeNode*> stk;
        TreeNode* lastNode = nullptr; //最近一次访问的节点

        TreeNode* cur = root;
        while (cur || !stk.empty()) {
            //让左路节点陷入栈
            while(cur) {
                stk.push(cur);
                cur = cur->left;
            }

            //因为实现的是后序遍历，所以根节点一定是最后访问的，为此我们要保证要先访问右子树再访问根节点
            //达到这个目的有两种情况：
            //1、根没有右子树，这样就直接访问根节点
            //2、根的右子树已经访问过了，这种情况的标志就是，lastNode是根的右孩子

            TreeNode* top = stk.top(); //获取左路节点，把左路节点当作根
            if (top->right == nullptr || top->right == lastNode)
            {
                ret.push_back(top->val);
                lastNode = top; //更新最近一次访问的节点
                stk.pop();
            }
            else //这种情况对应左路节点的右子树还没有访问，要先访问右子树再来访问左路节点
            {
                cur = top->right;
            }
        }

        return ret;
    }
};